package main

import "fmt"

/*
合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]
请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。


示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 */

func merge(intervals [][]int) [][]int {
	res := make([][]int, 0)
	length := len(intervals)
	var left, right int
	left = -1
	right = -1
	// 对输入数据按照左边界 进行插入排序
	for i := 0; i < len(intervals) - 1; i ++ {
		for j := i + 1; j > 0; j -- {
			if intervals[j][0] >= intervals[j - 1][0] {
				break   // 前面部分已经有序
			}
			intervals[j], intervals[j - 1] = intervals[j - 1], intervals[j]
		}
	}
	// fmt.Println(intervals)

	for i := 0; i < length; i ++ {
		if i + 1 < length && intervals[i][1] >= intervals[i + 1][0] {   // 说明可以合并
			if left == -1 {
				left = intervals[i][0]
			}
			if intervals[i][1] >= intervals[i + 1][1] {
				right = intervals[i][1]
			}else {
				right = intervals[i + 1][1]
			}
			continue

		}else {  // 不可以合并
			if left == -1 {
				left = intervals[i][0]
			}
			if right == -1 {
				right = intervals[i][1]
			}

		}
		res = append(res, []int{left, right})
		// 重置left, right
		left, right = -1, -1
		if i + 1 == length {
			break
		}
	}

	return res
}

func main() {
	// fmt.Println(merge([][]int{{1,3}, {2,6}, {8,10}, {15,18}}))
	fmt.Println(merge([][]int{{1,4}, {2,3}}))
}
